// 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
// 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
// nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
// 输入: nums1 = `[4,1,2]`, nums2 = `[1,3,4,2]`.
// 输出: `[-1,3,-1]`
// 解释:
// 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
// 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
// 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

// 思路：单调栈，对nums2需要维护单调递减栈，当nums2中当前元素比单调栈的栈顶元素大时，单调栈出栈
// 出栈的元素是索引，对nums1建立一个值和索引的map，这样通过nums2的值判断映射到npms1中，统计结果
// 时间复杂度：O(n)，n是nums2的长度
// 空间复杂度：O(n)，map的大小

function nextGreaterElement(nums1, nums2) {
    let result = new Array(nums1.length).fill(-1)
    let map = new Map
    for (let i = 0; i < nums1.length; i++) {
        map.set(nums1[i], i)        
    }
    let stack = [0]
    for (let i = 0; i < nums2.length; i++) {
        while (stack.length && nums2[stack[stack.length - 1]] < nums2[i]) {
            let index = stack.pop()
            if (map.has(nums2[index])) {
                result[map.get(nums2[index])] = nums2[i]
            }
        }   
        stack.push(i)     
    }
    return result
}

let nums1 = [4,1,2], nums2 = [1,3,4,2]
console.log(nextGreaterElement(nums1, nums2))